package com.easy.leetcode;

import java.util.*;

/**
 * @ClassName PermuteUnique47
 * @Description 47. 全排列 II
 * @Author zheng
 * @Date 2021/11/30 10:53
 * @Version 1.0
 **/
public class PermuteUnique47 {


    public List<List<Integer>> permuteUnique(int[] nums) {

        //返回结果
        List<List<Integer>> result = new ArrayList<>();
        //路径
        //List<Integer> path = new ArrayList<>();

        Deque<Integer> path = new ArrayDeque<>();
        //被访问数组
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums, result, path, used);

        return result;
    }

    /**
     * @return void
     * @Description 回溯
     * @Date 2021/11/30 10:56
     * @Param [nums] 数组
     **/
    public void backTracking(int[] nums, List<List<Integer>> result, Deque<Integer> path, boolean[] used) {
        //退出条件
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //已被访问，不能重复添加
            if (used[i]) {
                continue;
            }
            //已排序数组，如果与前一个值相同，会出现相同的数据，剪枝。
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.addLast(nums[i]);
            backTracking(nums, result, path, used);
            used[i] = false;
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        PermuteUnique47 permuteUnique47 = new PermuteUnique47();
        System.out.println(permuteUnique47.permuteUnique(new int[]{1, 1, 2}));
    }
}
